1. Technical Field
The invention is related to first-in-first-out (FIFO) queues employing non-blocking atomic compare-and-swap (CAS) instructions.
2. Background Art
A FIFO queue may be used by various application or process threads which may wish to enqueue or dequeue certain data on the queue. Typically, a queue is a list of different memory locations containing particular data, and each memory location is typically referred to as a xe2x80x9cnodexe2x80x9d of the queue. The nodes are kept in order by providing in each node a xe2x80x9cnextxe2x80x9d pointer that points to the memory location of the next node in the queue. The head of the queue is the first node (xe2x80x9chead nodexe2x80x9d) while the last node is the tail node. The tail node""s next pointer points to a predetermined number, such as NULL. A node is enqueued by inserting it at the tail so that it becomes the new tail node of the queue. This requires the thread to first determine which node is the current tail node. Nodes are dequeued at the head, so that the head node is dequeued and the next node becomes the head node. This requires the thread to first determine which node is the current head node. The queue has a head pointer pointing to the head node and a tail pointer pointing to the tail node.
Maintaining the integrity of the queue while permitting its concurrent use by a number of different threads is a difficult problem. To solve this problem, the queue design must address all possible pathological conditions that the queue could experience. For example, after one thread has identified the tail node in preparation for an enqueue operation, another thread may interrupt and enqueue another node onto the queue (which obsoletes the one node""s prior identification of the tail node). As another example: the head and tail nodes may be one and the same node because it is the only node on the queue; and one thread may identify the tail node in preparation for enqueueing a new node onto the queue; but, before it can, another thread may dequeue and move the tail node to another queue (for example) without changing its next pointer from NULL. In this case, the one thread may still succeed in attaching the new node to what it still believes is the tail node of the desired queue, but would actually be enqueueing the new node on the wrong queue. This latter case is typically referred to as the xe2x80x9cABA problemxe2x80x9d and is described extensively in the literature. It is plausible that such an event could occur even if there were more than one node on the queue in the following example: after the one thread identifies the tail node, actions by other threads cause the tail node to be moved to the head and then dequeued and re-enqueued on another queue before the one thread completes its enqueueing operation. In any case, the ABA problem entails the risk of a thread unknowingly enqueueing a new node on the wrong queue or other location.
Initially, the ABA problem was solved by providing, whenever one thread was in the middle of an enqueue or dequeue operation, a lock which protected the queue from being changed by another contending thread. However, such blocking queues are susceptible to large unpredictable delays in process execution, since a single thread can monopolize the queue, particularly if it is a low priority thread that is interrupted by other higher priority threads.
As a result, the art has sought a non-blocking queue (i.e., a queue with no locks) permitting concurrent access to the queue by more than one thread without suffering failures due to the ABA problem. In such a concurrent non-blocking queue, the ABA problem has been solved in ways that burden the queue and impair performance. One such concurrent non-blocking queue is described by Michael et al., xe2x80x9cSimple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,xe2x80x9d PODC, 1996. This publication describes a concurrent non-blocking queue in which the ABA problem is addressed by assigning an extra xe2x80x9ccountxe2x80x9d field to the queue pointers such as the next pointer of the tail node. Thus, for example, each time the tail node is modified by any thread, the count associated with the next pointer of the tail node would be incremented. In the ABA situation, if the tail node has been dequeued and re-enqueued on another node, a thread trying to enqueue a new node onto the first queue would recognize that the next pointer xe2x80x9ccountxe2x80x9d field of the what it believes to be tail node has changed, even if the next pointer still has the same value as before. Therefore the thread would not complete its enqueue operation, thereby preventing an ABA problem.
Another difficulty in the implementation of a non-blocking queue is the method of handling the case where the queue is empty; in other words, when there are no nodes in the queue. Support for enqueueing a node on an empty queue, or dequeueing the last node on a queue (leaving it empty) can greatly complicate the implementation, as each enqueue and dequeue operation would then need to maintain both the head and tail pointers. To simplify this case, the queue in the Michael publication keeps at least one node in the queue at all times. To implement this, the queue in the Michael publication must control the nodes, rather than letting threads enqueue or dequeue their own nodes. In the Michael publication, each node is selected from a list maintained for the queue. The data of interest is then stored in the node. Such data is taken from a thread and copied into the node for an xe2x80x9cenqueuexe2x80x9d operation. It is later copied out of the node and returned to a thread for a xe2x80x9cdequeuexe2x80x9d operation while the node itself is not, the node always being preserved for use with the queue. If the dequeue operation determines that the node being dequeued is the last node in the queue, it is left there to ensure that there is always at least one node in the queue.
The requirement that the queue allocate and deallocate the individual nodes constricts queue performance and constricts the manner in which threads may use the queue. This is especially true with regard to situations where the enqueue or dequeue operations may take place in an execution context from which memory allocation operations cannot be invoked (such as within an interrupt handler).
It is therefore desired to provide a concurrent non-blocking queue in which it is not necessary to maintain extra count fields and in which the threads themselves enqueue and dequeue any nodes they wish on the queue without any risk of emptying the queue.
The design described here differs from the Michael publication in two fundamental ways:
a) The use of a xe2x80x9cmagic numberxe2x80x9d (other than NULL) to be placed into the next pointer of the last node in the list, thus avoiding the use of a count and circumventing the ABA problem
b) The use of a dummy node to ensure that the queue is never empty, while still allowing the enqueue and dequeue of nodes managed outside of the control of the queue itself.
An application or thread enqueues a new node into the queue by, first, setting the next pointer of the new node to the magic number. If the next pointer of the current tail node points to the magic number, then its next pointer is changed to point to the new node. If this operation is successful, then the queue""s tail pointer is changed to point to the new node. If the foregoing conditions were not satisfied, then the tail pointer has been moved by another application or thread during the interim. This is corrected by changing the tail pointer to the next pointer of the node currently pointed to by the tail pointer. Then, the enqueue process is attempted again, and this cycle is repeated until successful.
An application or thread dequeues a node from the queue by, first, making local copies of the current version of the queue""s head pointer, tail pointer and the next pointer of the head node (the node pointed to by the head pointer). A check is then made to ensure that the queue""s head pointer has not changed, and then a check is made to ensure that the head and tail pointers do not point to the same thing. If they do, this indicates that either (a) the queue is empty or (b) another thread has changed the queue so that the tail pointer needs correcting. These two possibilities are resolved by checking whether the next pointer of the head node points to the magic number (in which case the queue is empty). If the queue is not empty, the tail pointer is corrected by changing it to point to the node pointed to by the next pointer of the node currently pointed to by the tail pointer. The foregoing dequeue process is then repeated until the above conditions are met. Once the above conditions are met (i.e., the head and tail pointers do not point to the same node), the current head node is dequeued by changing the head pointer to point to the node currently pointed to by the next pointer of the node being dequeued. Next, the dequeued node is checked to ensure that it is not the dummy node. If it is, then the dummy node is re-enqueued and the next node is dequeued as the one actually desired by the application.
In accordance with one aspect of the invention, a method is provided for one thread in a system running plural threads to enqueue a new node of its own choosing onto a selected FIFO queue, the system having plural FIFO queues, each queue including a succession of enqueued nodes and having a head pointer pointing to a head node and a tail pointer pointing to a tail node, each of the nodes having a next pointer, the next pointers of the enqueued nodes pointing to the next node in the succession from the head node to the tail node. The enqueueing method is carried out by first obtaining from the selected queue a queue-specific number of the selected queue unique to the selected queue. In this embodiment, this queue-specific number is used as the xe2x80x9cmagic numberxe2x80x9d. The next step is setting the next pointer of the new node to the queue-specific number. A determination is next made as to whether another one of the threads has preempted the one thread and, if so, updating the tail if needed and then re-starting the method. Otherwise, the next step is setting the next pointer of the tail node to point to the new node. The final step is setting the tail pointer to point to the new node if it has not been updated by another thread during the execution of the enqueueing method.
The step of determining whether another one of the threads has preempted the one thread includes making a local copy of the tail pointer of the selected queue and then determining whether the next pointer of the tail node of the selected queue no longer points to the queue-specific number of the selected queue. If the next pointer no longer points to the queue-specific number, a determination is made as to whether the tail pointer of the selected queue has changed since the local copy of the tail pointer was made.
The step of updating the tail pointer is needed if the tail pointer has not changed since the local copy was made, and is performed by changing the tail pointer to be equal to the next pointer of the tail node of the selected queue.
The step of setting the tail pointer to the new node if it has not been updated by another thread is carried out by first determining whether the tail pointer of the selected queue has not change since the making of the local copy. If the tail pointer has not changed since the making of the local copy, the tail pointer is changed by setting the tail pointer to point to the new node.
In the general case, the next pointer of the tail node of the queue initially points to the queue-specific number. The queue-specific number may be the address of the head pointer of the queue or the address of the tail pointer of the queue or a pointer having its low bit set to one or a system-wide unique identifier that is assigned to the queue at creation time, or some combination of the above, for example.
A dummy node having a next pointer is always present (although it may be temporarily dequeued by a thread). The next pointer of the dummy node points to a next node in the queue if the dummy is not currently the tail node and points to the queue-specific number if the queue is empty. In this way, the queue always contains at least one node.
In accordance with another aspect of the invention, a method is provided for one thread in a system running plural threads to dequeue a node from a selected one of the FIFO queues. The method is performed by first determining whether another thread has preempted the one thread and dequeued a node from the head of the queue and, if so, re-starting the method. Otherwise, the next step is determining, in the event the queue appears to be empty, whether another thread has preempted the one thread by enqueueing a new node at the tail of the queue, and if the other thread did not update the tail pointer, updating the tail pointer and re-starting the method. If the queue does not appear to be empty, the next step is determining whether another thread has preempted the one thread and dequeued a node from the head of the queue and, if so, re-starting the method. Otherwise, the head node is dequeued by changing the head pointer to equal the next pointer of the head node. Finally, if the dequeued node is a dummy node, the dummy node must be re-enqueued onto the queue. At this point, the thread may restart the dequeueing method with the new head node.
The step of determining whether another thread has preempted the one thread is preceded by first determining whether the queue appears to be empty. This is accomplished by determining whether the head pointer and the tail pointer point to the same node. If so, it is then determined whether the queue is actually empty by determining whether the next pointer of the head node points to the queue-specific number. If this is the case, the queue is considered empty and the operation is terminated.
The step of determining whether another thread has preempted the one thread and dequeued a node from the head is preceded by making a local copy of the head pointer, the tail pointer and the next pointer of the head node. The step of determining whether another thread has preempted the one thread and dequeued a node from the head consists of determining whether the head pointer has changed since the making of the local copy. The step of determining whether another thread has preempted the one thread and enqueued a new node at the tail consists of determining whether the tail pointer has changed since the making of the local copy. The step of determining whether the queue is empty consists of determining whether the next pointer of the head node is the queue-specific number. The step of updating the tail pointer consists of changing the tail pointer to equal the next pointer of the tail node (i.e., the node currently pointed to by the tail pointer).
In accordance with a further aspect of the invention, a method is provided for constructing a FIFO queue data structure. This method is carried out by first providing memory space for a head pointer, a tail pointer and a dummy node. Initially, the new queue will contain only the dummy node. The next step is to set the head pointer to point to the dummy node, set the tail pointer to pointer to the dummy node and set the next pointer of the dummy node to point to the queue-specific number.